import java.util.Arrays;
import java.lang.*;
public class HashBucket {
    static class Node{
        public int key;
        public int val;
        public Node next;

        public Node(int key,int val){
            this.key = key;
            this.val = val;
        }

    }
    public int usedSize = 0;

    public Node[] array = new Node[10];
    public static final double DEFAULT_LOAD_FACTOR = 0.75f;

    public int push(int key,int val) {
            int index = Math.abs(key % array.length);
            Node cur = array[index];
            while (cur != null) {
                if (cur.key == key) {//替换原来的value并且返回
                    int OlderValue = cur.val;
                    cur.val = val;
                    return OlderValue;
                }
                cur = cur.next;
            }
            //没有找到该节点
            //头插法
            Node node = new Node(key, val);
            cur = array[index];
            node.next = cur;
            array[index] = node;
            usedSize++;
            if (GetLode() > DEFAULT_LOAD_FACTOR) {
                resize();
            }
            return -1;
    }

    private void resize() {
        Node[] newArray = new Node[array.length*2];
        for (int i = 0;i<array.length;i++) {
            Node cur = array[i];
            while (cur!=null){
                Node curN = cur.next;
                int newIndex = cur.key%newArray.length;
                cur.next = newArray[newIndex];
                newArray[newIndex] = cur;
                cur = curN;
            }
        }
        array = newArray;
        //array = Arrays.copyOf(newArray,newArray.length);
    }

    private double GetLode() {
        return usedSize*1.0/array.length;//注意避免进行整数除法
    }
    public int getValue(int key){
        int index = Math.abs(key % array.length);
        Node cur = array[index];
        while(cur!=null) {
            if (cur.key == key) {
                return cur.val;
            }
            cur = cur.next;
        }
        return -1;
    }


}